﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/valid-triangle-number/
/*
题目描述：
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

 

示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:
输入: nums = [4,2,3,4]
输出: 4
 

提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
*/

// 开始解题：
// 方法1——二分查找法
// 先写一个函数，比较两个整数的大小
int cmp_int(const void* p1, const void* p2) {
    return *((int*)p1) - *((int*)p2);
}

int triangleNumber(int* nums, int numsSize) {
    // 先对数组进行排序
    qsort(nums, numsSize, sizeof(int), cmp_int);
    int i = 0;
    int j = 0;
    int answer = 0;
    for (i = 0; i < numsSize - 1; i++) {
        for (j = i + 1; j < numsSize; j++) {
            int left = j + 1;
            int right = numsSize - 1;
            int mid = 0;
            int k = j;
            while (left <= right) {
                mid = left + (right - left) / 2;
                if (nums[mid] < nums[i] + nums[j]) {
                    k = mid;
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
            answer += k - j;
        }
    }
    return answer;
}
// 时间复杂度：O(n^2logn)，n为数组的长度。
// 空间复杂度：O(logn)，空间复杂度主要取决于排序所需要的栈空间。